"""
难度：中等
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同
参考以下这颗二叉搜索树：
     5
    / \
   2   6
  / \
 1   3
示例 1：
输入: [1,6,3,2,5]
输出: false
示例 2：
输入: [1,3,2,6,5]
输出: true
提示：
数组长度 <= 1000
"""
"""
后序遍历的顺序为：左 -> 右 -> 根。而二叉搜索树的定义是：左子树所有节点值 < 根节点值，右子树所有节点值 > 根节点值。
所以，可以把数组最右侧元素作为二叉搜索树的根节点值。然后判断数组的左右两侧是否符合左侧值都小于该节点值，右侧值都大于该节点值。如果不满足，则说明不是某二叉搜索树的后序遍历结果。
找到左右分界线位置，然后递归左右数组继续查找。
终止条件为数组 开始位置 > 结束位置，此时该树的子节点数目小于等于 1，直接返回 True 即可。
"""

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        def verify(left, right):
            if left >= right:
                return True
            index = left
            while postorder[index] < postorder[right]:
                index += 1
            mid = index
            while postorder[index] > postorder[right]:
                index += 1
            
            return index == right and verify(left, mid - 1) and verify(mid, right - 1)
        
        if len(postorder) <= 2:
            return True
        return verify(0, len(postorder)-1)
